#include <iostream>

using namespace std;


struct Node{
	int data;
	Node *left;
	Node *right;
};

Node* Convert(Node* tree, Node **node)
{
	if(NULL == tree)
		return NULL;

	Node *head;
	if(NULL == tree->left){
		head = tree;
	}
	else{
		head = Convert(tree->left, node);
		tree->left = *node;
		(*node)->right = tree;		
	}

	if(NULL == tree->right){
		*node = tree;
	}
	else{
		tree->right = Convert(tree->right, node);
		tree->right->left = tree;
	}

	return head;
}

int mtmain(){
	Node * tree = new Node();
	tree->data = 4;
	tree->left = new Node();
	tree->left->data = 1;
	tree->left->right = new Node();
	tree->left->right->data = 2;
	tree->left->right->right = new Node();
	tree->left->right->right->data = 3;

	tree->right = new Node();
	tree->right->data = 6;
	tree->right->left = new Node();
	tree->right->left->data = 5;

	Node *node;
	Node *list = Convert(tree, &node);


	while(list){
		cout << list->data << endl;
		list = list->right;
	}
	while(node){
		cout << node->data << endl;
		node = node->left;
	}

	return 0;
}